#include <stdlib.h>
#include <stdio.h>
#include "bitree.h" //请不要删除，否则检查不通过
//广度优先算法
//注意内存分配

BiTNode* transform(CSNode *root){
    BiTNode *biroot = (BiTNode *)malloc(sizeof(BiTNode));
    if(biroot == NULL) return NULL;
    biroot->data = root->data;
    biroot->left = NULL;
    biroot->right = NULL;
    Queue *tree = create_queue();
    if(tree == NULL || root == NULL) return NULL;
    add_queue(tree , root);
    add_queue(tree , biroot);
    while (!is_empty_queue(tree)) {
        CSNode *p = (CSNode *)del_queue(tree);
        BiTNode *q = (BiTNode *)del_queue(tree);
        BiTNode *pre = NULL;
        for (int i = 0; p->children[i] != NULL; i++) {
            BiTNode *New = (BiTNode*)malloc(sizeof(BiTNode));
            if (New == NULL) {
                exit(0); 
            }
            New->data = p->children[i]->data;
            New->left = NULL;
            New->right = NULL;
            if (i == 0) {
                q->left = New;
                pre = New;
            }
            else {
                pre->right = New;
                pre = New;
            }
            add_queue(tree, p->children[i]);
            add_queue(tree, New);
        }
    }

    free_queue(tree);
    return biroot;

}